﻿using UnityEngine;
using System;
using System.Collections;
using System.Collections.Generic;

public struct Block
{
    public const byte Air = 0;
    public const byte Grass = 1;
    public const byte Stone = 2;
    public const byte Dirt  = 3;
    public const byte Sand  = 4;
    public const byte IronOre = 5;
    public const byte Bedrock = 6;

    //public static Block Air { get { return new Block(0); } }
    //public static Block Grass { get { return new Block(1); } }
    //public static Block Stone { get { return new Block(2); } }
    //public static Block Dirt { get { return new Block(3); } }
    //public static Block Sand { get { return new Block(4); } }
    //public static Block IronOre { get { return new Block(5); } }
    //public static Block Bedrock { get { return new Block(6); } }

    public static string[] BlockIDNames = new string[] { "Air", "Grass", "Stone", "Dirt", "Sand", "IronOre", "Bedrock" };

    public static bool operator ==(Block a, Block b)
    {
        return a.GetValue() == b.GetValue();
    }
    public static bool operator !=(Block a, Block b)
    {
        return !(a == b);
    }
    public override bool Equals(object obj)
    {
        return GetValue().Equals(((Block)obj).GetValue());
    }
    public override int GetHashCode()
    {
        return value;
    }

    public override string ToString()
    {
        return string.Format("BlockID: {0}", BlockIDNames[value]);
    }

    public Block(byte value)
    {
        this.value = value;
    }

    private byte value;

    public byte GetValue()
    {
        return value;
    }
    //public void SetValue(byte value)
    //{
    //    if ((value & 0x80) != 0)
    //    {
    //        throw new System.ArgumentException("The block value is higher than 127. The last bit is saved for walkable flag!");
    //    }
    //    this.value = value;
    //}
}

public class BinaryHeap<TKey, TValue>
{
    protected readonly IComparer<TKey> Comparer;
    protected readonly List<TKey> Keys;
    protected readonly List<TValue> Values;

    public BinaryHeap(IComparer<TKey> comparer)
    {
        this.Comparer = comparer;
        Keys = new List<TKey>();
        Values = new List<TValue>();
    }

    // O(N)
    public static BinaryHeap<TKey, TValue> Build(IEnumerable<KeyValuePair<TKey, TValue>> elements, IComparer<TKey> comparer)
    {
        var heap = new BinaryHeap<TKey, TValue>(comparer);
        foreach (var element in elements)
        {
            heap.Keys.Add(element.Key);
            heap.Values.Add(element.Value);
        }

        for (int i = (heap.Keys.Count - 2) >> 1; i >= 0; i--)
        {
            heap.BubbleDown(i);
        }

        return heap;
    }

    // O(logN)
    public virtual void Insert(TKey key, TValue value)
    {
        Keys.Add(key);
        Values.Add(value);
        BubbleUp(Keys.Count - 1);
    }

    // O(logN)
    public virtual KeyValuePair<TKey, TValue> ExtractMin()
    {
        if (Keys.Count == 0)
            throw new InvalidOperationException("Cannot extract minimum from empty heap.");

        var p = new KeyValuePair<TKey, TValue>(Keys[0], Values[0]);
        Swap(0, Keys.Count - 1);
        Keys.RemoveAt(Keys.Count - 1);
        Values.RemoveAt(Values.Count - 1);
        BubbleDown(0);
        return p;
    }

    protected virtual void Swap(int i, int j)
    {
        TKey tmpKey = Keys[i];
        TValue tmpVal = Values[i];

        Keys[i] = Keys[j];
        Values[i] = Values[j];

        Keys[j] = tmpKey;
        Values[j] = tmpVal;
    }

    protected void BubbleUp(int index)
    {
        while (index > 0)
        {
            int parent = (index - 1) >> 1;

            // stop condition: element is not less than it's parent
            if (Comparer.Compare(Keys[parent], Keys[index]) <= 0) return;
            Swap(index, parent);
            index = parent;
        }
    }

    // this is also called Heapify
    protected void BubbleDown(int index)
    {
        int lastParent = (Keys.Count - 2) >> 1;
        while (index <= lastParent)
        {
            int left = (index << 1) + 1;
            int right = left + 1;
            int min = index;
            if (left < Keys.Count && Comparer.Compare(Keys[left], Keys[min]) <= 0) min = left;
            if (right < Keys.Count && Comparer.Compare(Keys[right], Keys[min]) <= 0) min = right;

            // stop condition: index element is not less than both children
            if (min == index) return;
            Swap(index, min);
            index = min;
        }
    }
}

public class BinaryHeapWithUpdates<TKey, TValue> : BinaryHeap<TKey, TValue>
{
    protected readonly Dictionary<TValue, int> HeapIndexes;

    public BinaryHeapWithUpdates(IComparer<TKey> comparer, IEqualityComparer<TValue> valueComparer)
        : base(comparer)
    {
        HeapIndexes = new Dictionary<TValue, int>(valueComparer);
    }

    public void UpdateKey(TValue value, TKey newKey)
    {
        int index;
        if (!HeapIndexes.TryGetValue(value, out index))
            throw new ArgumentException("Value was not found in the heap.");

        var oldKey = Keys[index];
        int comp = Comparer.Compare(newKey, oldKey);
        Keys[index] = newKey;
        if (comp < 0)
        {
            // decrease-key
            BubbleUp(index);
        }
        else if (comp > 0)
        {
            // increase-key
            BubbleDown(index);
        }
    }

    public override void Insert(TKey key, TValue value)
    {
        HeapIndexes.Add(value, Keys.Count);
        base.Insert(key, value);
    }

    public override KeyValuePair<TKey, TValue> ExtractMin()
    {
        var min = base.ExtractMin();
        HeapIndexes.Remove(min.Value);
        return min;
    }

    protected override void Swap(int i, int j)
    {
        HeapIndexes[Values[i]] = j;
        HeapIndexes[Values[j]] = i;
        base.Swap(i, j);
    }
}